# 作者:小宇
# 2025年10月24日11时11分14秒
# 1225074067@qq.com
import random


class Sort:
    def __init__(self, n):

        self.len = n
        self.arr = [3, 87, 2, 93, 78, 56, 61, 38, 12, 40]
        # self.arr = [0] * n
        # self.random_data()

    def random_data(self):
        for i in range(self.len):
            self.arr[i] = random.randint(0, 99)

    def partition(self, left, right):
        arr = self.arr
        i = k = left
        random_pos = random.randint(left, right)
        arr[random_pos], arr[right] = arr[right], arr[random_pos]
        for i in range(left, right):
            if arr[i] < arr[right]:
                arr[i], arr[k] = arr[k], arr[i]
                k += 1
        arr[k], arr[right] = arr[right], arr[k]
        return k

    def quick_sort(self, left, right):
        if left < right:
            pivot = self.partition(left, right)
            self.quick_sort(left, pivot - 1)
            self.quick_sort(pivot + 1, right)

    def adjust_max_heap(self, pos, arr_len):
        arr = self.arr
        dad = pos
        son = 2 * dad + 1
        while son<arr_len:
            if (son + 1) < arr_len and arr[son] < arr[son + 1]:
                son += 1
            if arr[son] > arr[dad]:
                arr[son], arr[dad] = arr[dad], arr[son]
                dad = son
                son = dad * 2 + 1
            else:
                break

    def heap_sort(self):
        arr = self.arr
        for parent in range(len(arr) // 2 - 1, -1, -1):
            self.adjust_max_heap(parent, len(arr))
        arr[len(arr) - 1], arr[0] = arr[0], arr[len(arr) - 1]
        for arr_len in range(len(arr)-1,1,-1):
            self.adjust_max_heap(0,arr_len)
            arr[arr_len - 1], arr[0] = arr[0], arr[arr_len - 1]

        pass


if __name__ == '__main__':
    my_sort = Sort(10)
    # my_sort.quick_sort(0, 9)
    # print(my_sort.arr)
    my_sort.heap_sort()
    print(my_sort.arr)
